#include <bits/stdc++.h>
using namespace std;

/*
2749. 得到整数零需要执行的最少操作数
已解答
中等
相关标签
premium lock icon
相关企业
提示
给你两个整数：num1 和 num2 。

在一步操作中，你需要从范围 [0, 60] 中选出一个整数 i ，并从 num1 减去 2i + num2 。

请你计算，要想使 num1 等于 0 需要执行的最少操作数，并以整数形式返回。

如果无法使 num1 等于 0 ，返回 -1 。

 

示例 1：

输入：num1 = 3, num2 = -2
输出：3
解释：可以执行下述步骤使 3 等于 0 ：
- 选择 i = 2 ，并从 3 减去 22 + (-2) ，num1 = 3 - (4 + (-2)) = 1 。
- 选择 i = 2 ，并从 1 减去 22 + (-2) ，num1 = 1 - (4 + (-2)) = -1 。
- 选择 i = 0 ，并从 -1 减去 20 + (-2) ，num1 = (-1) - (1 + (-2)) = 0 。
可以证明 3 是需要执行的最少操作数。
示例 2：

输入：num1 = 5, num2 = 7
输出：-1
解释：可以证明，执行操作无法使 5 等于 0 。
 

提示：

1 <= num1 <= 109
-109 <= num2 <= 109
*/

// 法一
class Solution {
public:
    using ll = long long;
    int makeTheIntegerZero(int num1, int num2) {
        // 遍历可能的操作次数 找最小有效k
        for (int k = 1;  ; k++) {
            // s = num1 - k * num2
            ll s = (ll)num1 - (ll)k * num2;
            // nums2 > 0 k 增大到一定程度S会<=0 此时可终止循环
            if (s <= 0) {
                if (num2 >= 0)  break;
                else            continue;
            }
            // s不能超过最大可表示值
            if (s > (1LL << 61) - 1)    break;
            // 2^i_j至少为1，sum至少为k，故S必须≥k
            if (s < k)  continue;

            // 计算二进制1的个数 <= k
            int cnt = __builtin_popcountll(s);
            if (cnt <= k)       return k;

            // 当num2为非负数且k超过num1时，S必然≤0，提前终止
            if (num2 >= 0 && k > num1) break;
        }
        // 无效就回-1
        return -1;
    }
};

// 法二
class Solution {
public:
    int makeTheIntegerZero(int num1, int num2) {
        // 遍历可能的操作次数k，从1开始寻找最小有效解（k越小操作次数越少）
        // 循环条件：k <= num1 - num2 * k → 等价于 num1 - num2*k >= k（记S = num1 - num2*k）
        // 含义：S是k次操作中需要减去的所有2^i的总和（sum(2^i) = S）
        //       由于每个2^i ≥ 1，k个2^i的总和至少为k，因此S必须≥k才可能成立
        for (long long k = 1; k <= (long long)num1 - (long long)num2 * k; k++) {
            // 计算S = num1 - k*num2（需要由k个2^i的和组成）
            // popcount(S)：计算S的二进制表示中1的个数，即表示S所需的最少2^i的数量
            // 若k ≥ popcount(S)：说明可以通过拆分2^i（如将2^3拆分为2^2+2^2）得到k个项，满足sum为S

			/////////////////////////////////////////////
			/// The number of bits set in `x`.
			//   template<__unsigned_integer _Tp>
			//     constexpr int
			//     popcount(_Tp __x) noexcept
			// { return std::__popcount(__x); }
			/////////////////////////////////////////////

    
            if (k >= popcount((uint64_t) num1 - num2 * k)) {
                return k; // 找到最小有效k，返回
            }
        }
        // 遍历完所有可能的k仍无有效解，返回-1
        return -1;
    }
};